package leetcode;

public class PartionEqualSubSets {

	public static void main(String[] args) {
		int[] nums = { 66, 90, 7, 6, 32, 16, 2, 78, 69, 88, 85, 26, 3, 9, 58,
				65, 30, 96, 11, 31, 99, 49, 63, 83, 79, 97, 20, 64, 81, 80, 25,
				69, 9, 75, 23, 70, 26, 71, 25, 54, 1, 40, 41, 82, 32, 10, 26,
				33, 50, 71, 5, 91, 59, 96, 9, 15, 46, 70, 26, 32, 49, 35, 80,
				21, 34, 95, 51, 66, 17, 71, 28, 88, 46, 21, 31, 71, 42, 2, 98,
				96, 40, 65, 92, 43, 68, 14, 98, 38, 13, 77, 14, 13, 60, 79, 52,
				46, 9, 13, 25, 8 };
		PartionEqualSubSets object = new PartionEqualSubSets();
		object.canPartition(nums);
	}

	public boolean canPartition(int[] nums) {
		if (nums == null || nums.length <= 0) {
			return true;
		}
		int sum = 0;
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];
		}
		System.out.println("sum:" + sum);
		if ((sum & 1) != 0) {
			return false;
		}
		sum = sum / 2;
		// int curSum = nums[0];
		// int left = 0;
		// int right = 0;
		// //之所以不能这样写的原因是这是求子数组的，而这道题是子集，子集是包含元素，不必连续
		// while (right < nums.length) {
		// if (curSum == sum) {
		// return true;
		// } else if (curSum > sum) {
		// curSum -= nums[left++];
		// } else {
		// right++;
		// if (right == nums.length) {
		// break;
		// // return false;
		// }
		// curSum += nums[right];
		// }
		// }
		// System.out.println("curSum:" + curSum);

		sum /= 2;
		
		//对空间进行压缩之后：Runtime: 36 ms
		boolean[] dp = new boolean[sum + 1];
		// dp init
		dp[0] = true;
		// dp transition
		for (int i = 0; i < nums.length; i++) {
			//注意，这里要从右往左遍历，因为需要的是小于或者等于j的dp值
			//如果从左往右遍历，可能会更新j的值，比如j = 2的时候，进行了更新
			//后面需要计算4的时候，dp[4 - 2]可能会用到j = 2，造成错误
			
			//而从右往左更新的时候是更新的大值，后面肯定不会用到该值
			for (int j = sum; j >= nums[i]; j--) {
				//因为j 小于nums[i]的时候dp[i][j] = dp[i - 1][j]也就是说不用更新
				dp[j] = dp[j] || dp[j - nums[i]];
			}
			
			//如果加上这个避免不必要的操作
			//Runtime: 19 ms
			if(dp[sum]){
			    return true;
			}
		}
		return dp[sum];
	}

	//使用动态规划
	//Runtime: 51 ms
	public boolean canPartition2(int[] nums) {
		if (nums == null || nums.length <= 0) {
			return true;
		}
		int sum = 0;
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];
		}
		if ((sum & 1) != 0) {
			return false;
		}
		sum = sum / 2;
		//dp[i][j]表示前[i]个元素 是否有和为j 子集
		boolean[][] dp = new boolean[nums.length][sum + 1];
		// dp init
		// deal with the first row
		// nums[0] <= sum in case of arrayIndexOf
		if (nums[0] <= sum)
			dp[0][nums[0]] = true;
		for (int i = 0; i < nums.length; i++) {
			dp[i][0] = true;
		}
		// dp transition
		for (int i = 1; i < nums.length; i++) {
			for (int j = 1; j <= sum; j++) {
				if (j < nums[i]) {
					dp[i][j] = dp[i - 1][j];
				} else {
					dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
				}
			}
		}
		return dp[nums.length - 1][sum];
	}
}
